#include <iostream>
#include <random>
#include <cmath>
#include <ctime>
#include <vector>
#include <algorithm>
/*要求我们计算给定序列的最小和问题
即计算每一个元素前面小于当前元素的元素和是多少*/
using namespace std;
/*暴力法求解最小和问题*/
int violence_Sum(std::vector<int>& v)
{
	int sum = 0;
	for (int i = 1; i < v.size(); ++i)
	{
		/* code */
		for (int j = 0; j < i; ++j)
		{
			/* code */
			if(v[j]<v[i])
				sum+=v[j];
		}
	}
	return sum;
}
/*二路归并求最小和问题*/
class mergeSort
{
	friend class comparator;
public:
	mergeSort();
	~mergeSort();
	static void merge(std::vector<int> &v,size_t left,size_t mid,size_t right,int &sum);
	static void sort(std::vector<int> &v,size_t low,size_t high,int &sum);
};
void mergeSort::sort(std::vector<int> &array,size_t low,size_t high,int &sum){
	if (low<high)
	{
		size_t mid = low + ((high-low)>>1);		//更加安全，可以防止数组过大发生溢出
		sort(array,low,mid,sum);
		sort(array,mid+1,high,sum);
		merge(array,low,mid,high,sum);
	}
}
void mergeSort::merge(std::vector<int> &array,size_t low,size_t mid,size_t high,int &sum){
	int i=low;
	int j=mid+1;
	while(i<=mid&&j<=high)
	{
		if(array[i]>array[j])
			{
				j++;
			}
		else if(array[i]<array[j])
		{
			sum+=array[i]*(high-j+1);
			i++;
		}
		else 
		{
			j++;
		}
	}
	std::vector<int> help;
	size_t p1=low;
	size_t p2=mid+1;
	while(p1<=mid&&p2<=high){
		int value = array[p1]<=array[p2]?array[p1++]:array[p2++];	//为保证算法的稳定性，此处需要使用<=,此处假设升序排列
		help.push_back(value);
	}
	while(p1<=mid){
		help.push_back(array[p1++]);
	}
	while(p2<=high){
		help.push_back(array[p2++]);
	}
	auto ivec=array.begin()+low;
	for(auto value:help){
		*ivec = value;		//可合并为*ivec++=value;
		ivec++;
	}
}
//传说中的对数器   
class MinSum 
{
public:
	std::vector<int> geneArr()
	{
		static default_random_engine e(time(0));
		static uniform_int_distribution<int> u(-1000,10000);
		std::vector<int> v;
		for(size_t i=0;i<abs(u(e)%100);i++){
			v.push_back(u(e));
		}
	// static uniform_int_distribution<int> u(1,10);//设个小的，进行人工计算
	// std::vector<int> v;
	// for(size_t i=0;i<7;i++){
	// 	v.push_back(u(e));
	// }
		return v;
	}
	void operator()(){
		std::vector<int> array1 = geneArr();
		std::vector<int> array2(array1);
		for(auto value:array2){
			cout<<value<<" ";
		}
		cout<<endl;
		int sum1=violence_Sum(array1);
		cout<<sum1<<endl;
		int sum2 = 0 ;
		mergeSort::sort(array2,0,array2.size()-1,sum2);
		cout<<sum2<<endl;
	}
};

int main(){
	MinSum comparator;
	comparator();
	return 0;
}
